package org.example.leetcode;


import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.List;

/**
 * 动态规划
 */
public class DongTaiGuiHua {


    //该问题的思路是：到达哪个台阶就需要付出该到达的台阶的所需的费用
    //还有一种是到达哪个台阶是不需要花费费用的，跳出这个台阶就需要花费该台阶的费用
    public static int minCostClimbingStairs(int[] cost) {
        if (cost.length == 2) {
            return cost[cost.length - 1];
        }
        int[] dp = new int[cost.length + 2];//dp[i] 爬到第i层所需要的最小的总费用
        dp[1] = cost[0];
        dp[2] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i + 1] = Math.min(dp[i - 1], dp[i]) + cost[i];
        }
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }


    public static int minCostClimbingStairs1(int[] cost) {
        int[] dp = new int[cost.length + 1];//dp[i] 爬到第i层所需要的最小的总费用(不需要付第i层的费用，只需要付之前台阶的费用）
        dp[0] = 0;//到达第0层台阶需要的费用
        dp[1] = 0;//从第0层台阶到达第1层台阶，需要付出跳出0层台阶的费用，第零层的为0 所以dp1也为0
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        //dp.length -1，是跳出该台阶的费用,这里不需要做直接跳出台阶或者跳到最后一个台阶的判断
        return dp[dp.length - 1];
    }

    @Test
    public void test001() {
        System.out.println(minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));

    }

    /**
     * 机器人的路径
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //机器人到达某个位置A,只能是从上到下，或者从左到右，
        // 所以这里只需要 dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
        //dp[i][j - 1] 同行不同列，表示从左到右
        //dp[i - 1][j] 同列不同行，从上到下

        //这里初始化的原理，上面的递推公式是从上到下从左到右，而0行n列 以及0列n行的
        //不适合该公式，故需要作为初始化来解决


        //初始化第一行

        Arrays.fill(dp[0], 1);

        //初始化第一列
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }


    /**
     * 机器人路径，有阻塞
     *
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //如果起始点和终点有阻塞的就直接返回0
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }
        int[][] dp = new int[m][n];
        //初始化
        //初始化列，注意这里要判断如果有石头就不继续初始化了，后面的都默认是0
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;//初始化第一列
        }
        //初始化行，注意这里要判断如果有石头就不继续初始化了，后面的都默认是0
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;//初始化第一行
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;//有石头不能正常通行
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//可以正常通行
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    @Test
    public void test002() {
        int i = uniquePathsWithObstacles(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}});
        System.out.println(i);
    }


    /**
     * 动态规划，花费体力值爬楼梯
     * 第一步不支付费用
     *
     * @param cost
     * @return
     */
    public int minCostClimbingStairs2(int[] cost) {
        if (cost.length <= 1) {
            return 0;
        }
        //这里加1的原因是，从第n 或者 第n-1阶跳出来，需要计算第n 或者n-1的最小费用，这个 最后一个的值就是最小费用
        int[] dp = new int[cost.length + 1];
        //这里默认是从第上阶跳到当前阶层，不需要花费当前阶层的费用，只需要支付上层阶层的费用
        //同理，从当前阶跳到后面一阶，只需要支付当前阶层的费用
        dp[0] = 0;//跳到第0阶是不需要花费费用的
        dp[1] = 0;//到第一阶也是不需要花费费用的

        for (int i = 2; i <= cost.length; i++) {
            //这种是错误的，dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i-1];
            dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i-2]) + cost[i-2];
        }
        return dp[dp.length -1];
    }


    @Test
    public void test003(){
        String[] str = new String[]{
                "111","222","333"
        };
        List<String> list = Arrays.asList(str);
        for (String s : list) {
            if(s.equals("111")){
                list.remove(2);
            }

        }
    }


}
